; 1 Linear Recursion and Iteration
; recur: need to memo the defered operation
; iter: no need to memo! 
;       the state can be summarized by a fixed # of state vars!
;       and fixed rules to update state
(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1))))
)
(factorial 9)
(define (factorial n)
    (define (fact-iter product count)
        (if (= count n)
            (* product count)
            (fact-iter (* product count) (+ count 1)))
    )
    (fact-iter 1 1)
)
(factorial 9)
; another perspective
; iter: hold all info about the state!
; recur: there is some "hidden" info about "where the program is" 
;        maintained by interpreter, not repr. by var

; 2 Tree Recursion
; fib recur: exponential compliacted
(define (<= a b)
    (or (< a b) (= a b)))

(define (fib n)
    (if (or (= n 1) (= n 0))
        1
        (+ (fib (- n 1)) (fib (- n 2))))
)
; modify into iter way
(define (fib n)
    (define (fib-iter count a b)
        (if (<= count n)
            (fib-iter (+ count 1) (+ a b) a)
            a)
    )
    (if (or (<= n 1))
        1
        (fib-iter 2 1 1))
)
(fib 5)
; Example: Money Changing
; Given 50, 25, 10, 5, 1 and total money M. Output # of decomposition
; recur/ but dp is better
(define (money_changing M kinds demonination)
    (define (recur M kinds)
        (cond ((= M 0) 1)
            ((< M 0) 0)
            ((= kinds 0) 0)
            (else (+ (recur M (- kinds 1)) (recur (- M (demonination kinds)) kinds))))
    )
    (recur M kinds)
)
(define (demonination kinds)
        (cond ((= kinds 5) 50)
            ((= kinds 4) 25)
            ((= kinds 3) 10)
            ((= kinds 2) 5)
            ((= kinds 1) 1)
        )
    )
(money_changing 100 5 demonination)

; 3 Order of Growth

; 4 Exponential
(define (fast_exp b n)
    (if (= n 1)
        b
        (if (= (remainder n 2) 0) 
            (square (fast_exp b (/ n 2)))
            (* b (square (fast_exp b (/ (- n 1) 2))))
        )
    )
)
(fast_exp 11 1000)
; iter version is in the Ex1_2

; 5 GCD
; GCD(a,b) = GCD(b,r)
(define (gcd a b)
    (if (< a b)
        (gcd b a)
        (if (= b 0)
            a
            (gcd b (remainder a b))
        )
    )
)
(gcd 100 240)

; 6 Testing for Primality
; O(sqrt N) method
(define (prime? x)
    (define (iter n)
        (if (> (* n n) x)
            #t
            (if (= 0 (remainder x n))
                #f
                (iter (+ n 1))
            )
        )
    )
    (cond ( (= x 1) #f)
        ((= x 2) #t)
        (else (iter 2))
    )
)
(prime? 23)
; probalitic O(log N) method
; Fermat test
; Fermat Little Thm
; if n is prime, 0<a<n; then a^n mod n and a is the same.
; if n is not prime , the relation is highly likely not satisfied!

; at first try to reuse fast_exp directly
; but we only care about the remainder! 
; we can re-write fast_exp to make it even faster(based on the same idea)
; for we do not need to cal very big exp!
(define (square x)
    (* x x)
)
(define (expmod b n m)
    (if (= n 1)
        (remainder b m)
        (if (= 0 (remainder n 2))
            (remainder (square (expmod b (/ n 2) m)) m)
            (remainder (* b (square (expmod b (/ (- n 1) 2) m))) m)
        )
    )
)
; fast_exp for sanity check
(define (fast_exp b n)
    (define (iter a b n)
        (if (= n 0)
            a
            (if (= 0 (remainder n 2))
                (iter a (* b b) (/ n 2))            
                (iter (* a b) (* b b) (/ (- n 1) 2))
            )
        )
    )
    (iter 1 b n)
)
; (fast_exp 5 11)
; (remainder (fast_exp 5 11) 11)
(define (fermat_prime? n times)
    (define (iter cnt)
        (define guess (+ 1 (random (- n 1))))
        (if (= cnt times)
            #t
            (if (= (expmod guess n n)  guess ) 
                (iter (+ cnt 1))
                #f
            )
        )
    )
    (iter 0)
)
; (expmod 5 15 15)
(fermat_prime? 71 30)

